

public class fastSparseArray<T> {
	public static class node<T> {
		node<T> nextNode;
		T data;
		int key;
		node(T dat) {
			data = dat;
		}
		node(T dat,int ke) {
			data = dat;
			key = ke;
		}
		node() {
			data = null;
		}
	}
	node nodeArray[];
	int keyRangeStart, keyRangeEnd;
	int approxNumEntries;
	int arraySize;
	node tempNode;
	T defaultValue;
	fastSparseArray(int keyStart, int keyEnd, int approxEntries) {
		keyRangeStart = keyStart;
		keyRangeEnd = keyEnd;
		approxNumEntries = approxEntries;
		arraySize = approxNumEntries * 2;
		nodeArray = new node[arraySize];
		for(int i=0; i < arraySize; i++) nodeArray[i] = new node<T>();
	}
	void setDefaultValue(T val) { defaultValue = val; };
	int hash(int key) {
		return (key % arraySize);
	}
	Object get(int key) {
		int arval = hash(key);
		if(nodeArray[arval] == null) return defaultValue;
		else {
			node<T> tempNode = nodeArray[arval];
			while(tempNode.nextNode != null && tempNode.key != key) {
				tempNode = tempNode.nextNode;
			}
			if(tempNode.key == key) return tempNode.data;
			else return defaultValue;
		}
	}
	int length() {
		return (keyRangeEnd - keyRangeStart);
	}
	@SuppressWarnings("unchecked")
	void update(int key, Object dat) { add(key,dat); };
	void add(int key, Object dat) {
		int arval = hash(key);
		if(nodeArray[arval].data == null) nodeArray[arval] = new node<T>((T)dat,key);
		else if(nodeArray[arval].key == key) nodeArray[arval].data = dat;
		else {
			node<T> tempNode = nodeArray[arval];
			while(tempNode.nextNode != null && tempNode.key != key) {
				tempNode = tempNode.nextNode;
			}
			if(tempNode.key != key) tempNode.nextNode = new node<T>((T)dat,key);
			else tempNode.data = (T)dat;
		}
	}
}
